package 剑指Offer65.不用加减乘除做加法;

/**        非进位   有进位
 * 0   0     0        0
 * 0   1     1        0
 * 1   0     1        0
 * 1   1     0        1
 *         异或       与（要左移以为）
 * 因此
 *      非进位n：a(i)=a(i)^b(i)  i表示位
 *      有进位c：a(i+1)=a(i)&b(i)
 * 减法如何处理：因为有补码，所以不影响结果
 * 负数补码：各位取反（不包括符号位），末位加一（包括符号位得进位）
 * 100000 和 000000 正0和负0的补码都是一样的
 * 有人会问
 * 10000000这个补码表示的哪个数的补码呢？
 * 其实这是一个规定，这个数表示的是-128
 *  3  的补码  00000011
 * -8  的补码  11111000
 *
 * 时间：O（1） 最坏32次递归
 * 空间：O(1)
 */
class Solution {
    // 把非进位复制给a,把进位赋值给b,递归直到b=0
    public int add(int a, int b) {
        if(b==0){
            return a;
        }
        // 等于先算一圈a和b不进位相加，再把结果和进位的相加
        return add(a^b,(a&b)<<1);
    }
}